package euler.p051_100;

import euler.MainEuler;

public class Euler071 extends MainEuler {

    /*
        Consider the fraction, n/d, where n and d are positive integers.
        If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

        If we list the set of reduced proper fractions for d ≤ 8
        in ascending order of size, we get:

        1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2,
        4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

        It can be seen that 2/5 is the fraction immediately to the left of 3/7.

        By listing the set of reduced proper fractions
        for d ≤ 1,000,000 in ascending order of size,
        find the numerator of the fraction immediately to the left of 3/7.
     */

    // http://en.wikipedia.org/wiki/Farey_sequence
    public String resolve() {

        int limite = 1000000;
        int bestNum = 0;
        int bestDenum = 1;

        for (int denum = 1; denum <= limite; denum++) {
            for (int num = (int)(bestNum*(long)denum/bestDenum) + 1; num < (3.0*denum)/7; num++) {
                bestNum = num;
                bestDenum = denum;
            }
        }

        return String.valueOf(bestNum/primeHelper.MCD(bestNum, bestDenum));
        // 428570
    }

}
